#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <sys/time.h>

typedef struct _COORDENADAS{
	int linha;
	int coluna;
}Coordenadas;

int indice(int l,int c,int k){
	return l*k+c;
}

Coordenadas coordenada(int indice,int k){
	Coordenadas coord;
	coord.linha=indice / k ;
	coord.coluna=indice % k;
	return coord;
}

void imprimeMatriz(int m,int k,int *matriz){
	int i,j;

	printf("\n");
	for(i=0;i<m;i++){
			for(j=0;j<k;j++){
				if ((*(matriz+indice(i,j,k))>=0)&&*(matriz+indice(i,j,k))<100){
					printf(" ");
				}
				if ((*(matriz+indice(i,j,k))>-10)&&*(matriz+indice(i,j,k))<10){
									printf(" ");
				}
				if ((*(matriz+indice(i,j,k))>-100)&&*(matriz+indice(i,j,k))<=100){
					printf(" ");
				}
				printf("%d ",*(matriz+indice(i,j,k)));
			}
			printf("\n");
		}
}

void preencheMatriz(int m,int k,int *matriz){
	int i;
	for(i=0;i<m*k;i++){
			*(matriz+i)= rand()%101;
			if (rand()%2==0){
				*(matriz+i)*=-1;
			}
		}
}

int encontraMax(int m,int k,int *matriz){
	int i,maximo;
	maximo = *matriz;
	for(i=0;i<m*k-1;i++){
		maximo = *(matriz+i)>maximo?*(matriz+i):maximo;
	}
	return maximo;
}

int encontraMin(int m,int k,int *matriz){
	int i,minimo;
	minimo = *(matriz+1);
		for(i=0;i<m*k;i++){
			minimo = *(matriz+i)<minimo?*(matriz+i):minimo;
		}
		return minimo;
}

void encontraNumero(int numero,int *matriz,int m,int k,Coordenadas *coorVector){

	int j=0,i=0;

	for(i=0;i<m*k;i++){
		if(matriz[i]==numero){
			coorVector[j]=coordenada(i,k);
			j++;
		}
	}

	coorVector[j].coluna=-1;
	coorVector[j].linha=-1;

}

void imprimeCoordenadas(Coordenadas *vec){
	Coordenadas coord;
	int j=0;
	while(1){
	coord = vec[j];
	if (coord.linha ==-1) break;
	printf("Linha : %d Coluna %d\n",vec[j].linha,vec[j].coluna);
	j++;
	}

}


//calcular os produtos internos
void calculaProdutosInternos(int m, int k, int *matriz, int *produtoInterno){
	int i;
	int j;
	for (i=0; i< m; i++){
		produtoInterno[i] = 0;
		for (j=0; j< k; j++){
			produtoInterno[i] += ( *(matriz+indice(i,j,k)) * *(matriz+indice(j,i,k)));
		}
	}
}

//encontra maior produtoInterno
void encontraMaxProdutoInterno(){

}

//encontra menor produtoInterno
void encontraMinProdutoInterno(){

}

//calcula desvio padrao
double desvioPadraoProdutos(int m, int *produtoInterno){

	int i;
	double acumulador = 0;
	for (i=0; i<m; i++){
		acumulador += produtoInterno[i];
	}
	acumulador = (acumulador / m); //aqui o acumulador tem a media dos valores do prod. interno

	i = 0;
	double acumulador2 = 0;
	for (i=0; i<m; i++){
		acumulador2 += pow((produtoInterno[i] - acumulador),2); //desvios medios ao quadrado
	}
	acumulador2 = (acumulador2 / m); //aqui acumulador2 tem a variancia

	//testando
	printf("\n----acumulador: %f\n", acumulador);
	printf("\n----produtoInterno[3]: %d\n", produtoInterno[3]);
	printf("\n----acumulador2: %f\n", acumulador2);

	//acumulador2 = pow(acumulador2, 0.5); //aqui acumulador2 tem o desvio padrao
	//acumulador2 = sqrt(acumulador2);
	//testando
	printf("\n----acumulador2: %f\n", acumulador2);

	return acumulador2;
}


int main(int argc,char **argv){
	struct timeval alfa, omega;

	srand(time(NULL));

	int m,k,*matriz,*produtoInterno;

	printf("Versao 1\nEntre com o numero de linhas e colunas respectivamente.\n");

	scanf("%d %d",&m,&k);

	printf("inicializando uma matriz com %d colunas e %d linhas",k,m);

	matriz=(int*)malloc(sizeof(int)*m*k);

	//falta verificar quantos produtos internos eu terei
	produtoInterno=(int*)malloc(sizeof(int)*m);

	preencheMatriz(m,k,matriz);
//	imprimeMatriz(m,k,matriz);
	int max = encontraMax(m,k,matriz);
	int min = encontraMin(m,k,matriz);
	printf("\nValor máximo:%d , Valor mínimo:%d \n",max,min);

	Coordenadas coorMaxs[m*k+1];
	encontraNumero(max,matriz,m,k,coorMaxs);
	Coordenadas coorMins[m*k+1];
	encontraNumero(min,matriz,m,k,coorMins);

	printf("\nCoordenadas dos menores valores\n\n");
	imprimeCoordenadas(coorMins);
	printf("\nCoordenadas dos maiores valores\n\n");
	imprimeCoordenadas(coorMaxs);


	printf("\nComecando a calcular produtos internos...");
	gettimeofday(&alfa, NULL);

	//calcula produto interno
	calculaProdutosInternos(m,k,matriz,produtoInterno);
	imprimeMatriz(m,1,produtoInterno);

	//!!!!!!!!!!!!! NAO ESTA DETECTANDO CORRETAMENTE !!!!!!!!!!!!! --acho que esta desconsiderando o ultimo prod. interno -- talvez o erro se estenda a outros lugares
	//encontra maior produto interno
	int maxProdutoInterno = encontraMax(m,1,produtoInterno);
	printf("\nMaior produto interno: %d\n", maxProdutoInterno);

	//!!!!!!!!!!!!! NAO ESTA DETECTANDO CORRETAMENTE !!!!!!!!!!!!! --acho que esta desconsiderando o ultimo prod. interno
	//encontra menor produto interno
	int minProdutoInterno = encontraMin(m,1,produtoInterno);
	printf("\nMenor produto interno: %d\n", minProdutoInterno);


	//coordenadas dos maiores e menores produtos internos
	Coordenadas coorMaxsProdutosInternos[m];
	encontraNumero(maxProdutoInterno, produtoInterno,m,1,coorMaxsProdutosInternos);
	Coordenadas coorMinsProdutosInternos[m];
	encontraNumero(minProdutoInterno, produtoInterno,m,1,coorMinsProdutosInternos);

	//imprime as coordenadas do maior produto interno
	printf("\nCoordenadas do maior produto interno:\n\n");
	imprimeCoordenadas(coorMaxsProdutosInternos);
	//imprime as coordenadas do menor produto interno
	printf("\nCoordenadas do menor produto interno:\n\n");
	imprimeCoordenadas(coorMinsProdutosInternos);


	//imprime desvio padrao dos produtos internos
	double desvioPadraoProdutosInternos = desvioPadraoProdutos(m, produtoInterno);
	printf("\nDesvio padrao dos produtos internos: %f\n", desvioPadraoProdutosInternos);


	gettimeofday(&omega, NULL);
	int seconds  = omega.tv_sec  - alfa.tv_sec;
	float useconds = (omega.tv_usec - alfa.tv_usec)/1000000.0;
	printf("\nTempo de execucao em segundos: %f\n", seconds+useconds);


	return 0;
}

